package demo;

import java.util.*;

/**
 *  二叉树的层序遍历
 */
class Solution12 {
	public List<List<Integer>> levelOrder(TreeNode root) {
		if(root == null) {
			return new ArrayList<>();
		}
		List<List<Integer>> res = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while(!queue.isEmpty()){
			int count = queue.size();
			List<Integer> list = new ArrayList<>();
			while(count > 0){
				TreeNode node = queue.poll();
				list.add(node.val);
				if(node.left != null) {
					queue.add(node.left);
				}
				if(node.right != null) {
					queue.add(node.right);
				}
				count--;
			}
			res.add(list);
		}
		return res;
	}

	public static void main(String[] args) {
		TreeNode treeNode3 = new TreeNode(3);
		TreeNode treeNode9 = new TreeNode(9);
		TreeNode treeNode20 = new TreeNode(20);
		TreeNode treeNode15 = new TreeNode(15);
		TreeNode treeNode7 = new TreeNode(7);
		treeNode3.left = treeNode9;
		treeNode3.right = treeNode20;
		treeNode20.left = treeNode15;
		treeNode15.right = treeNode7;

		System.out.println(new Solution12().levelOrder(treeNode3));
	}
}

